package 链表;

/**
 * ---------------------------------------------------------
 * <h>https://leetcode-cn.com/problems/palindrome-linked-list/</h>
 * <p>请判断一个链表是否为回文链表。
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 *
 * 示例 2:
 *
 * 输入: 1->2->2->1
 * 输出: true
 * 进阶：
 * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 *
 * </p>
 * Created by Frank on 2021/3/29.
 * <a href="mailto:frankyao10110@gmail.com">Contact me</a>
 * ---------------------------------------------------------
 */
public class _回文链表 {

    public static void main(String[] args) {
        ListNode list = new ListNode(5);
        list.next = new ListNode(1);
        list.next.next = new ListNode(2);
        list.next.next.next = new ListNode(2);
        list.next.next.next.next = new ListNode(1);
        list.next.next.next.next.next = new ListNode(5);
//        list.next.next.next.next.next.next = new ListNode(5);

//        System.out.println("midNode: " + findMiddle(list).val);
        System.out.println("isPalindrome: " + isPalindrome(list));
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        if (head.next.next == null) return head.val == head.next.val;
        //找到链表中间节点（快慢指针）
        //将后半部分链表反转（反转链表）
        //判断前半部分和后半部分是否相等
        //恢复链表
        ListNode mid = findMiddle(head);
        System.out.println("mid: " + mid.val);
        ListNode rvNode = reverse(mid.next);
        ListNode rvNodeHead = rvNode;

        boolean isPalindrome = true;
        while (rvNode != null) {
            System.out.println("head: " + head.val + " mid.next: " + rvNode.val);
            if (head.val != rvNode.val) {
                isPalindrome = false;
                break;
            }

            head = head.next;
            rvNode = rvNode.next;
        }

        reverse(rvNodeHead);

        return isPalindrome;
    }

    private static ListNode findMiddle(ListNode head) {

        ListNode slow = head.next;
        ListNode fast = head.next.next;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private static ListNode reverse(ListNode head) {
        return _反转链表.reverseList(head);
    }
}
